#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    int maximumRemovals(string s, string p, vector<int> &removable)
    {
        int left = 0, right = removable.size();
        auto check = [&](int n)
        {
            vector<bool> valid(s.size(), true);
            for (int i = 0; i < n; i++)
            {
                valid[removable[i]] = false;
            }
            int ids = 0, idp = 0;
            while (idp < p.size())
            {
                if (ids > s.size())
                    return false;
                if (valid[ids] && s[ids] == p[idp])
                {
                    ids++;
                    idp++;
                }
                else
                {
                    ids++;
                }
            }
            return true;
        };
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (check(mid))
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
};
int main()
{
    cout << "Code1898" << endl;
    Solution s;
    string ss = "qlevcvgzfpryiqlwy";
    string ps = "qlecfqlw";
    vector<int> remove = {12, 5};
    cout << s.maximumRemovals(ss, ps, remove) << endl;
    return 0;
}
//for basic loop O(n) x O2(n) if do not know how to optimize O2(n), just binary search. 